1. Field of Invention
The present invention relates generally to data communication systems. More particularly, the present invention relates to systems and methods for substantially automating the computation of a circuit path through a bi-directional line switched ring that meets common time slot requirements.
2. Description of the Related Art
The demand for data communication services is growing at an explosive rate. Much of the increased demand is due to the fact that more residential and business computer users are becoming connected to the Internet. Furthermore, the types of traffic being carried by the Internet are shifting from lower bandwidth applications towards high bandwidth applications which include voice traffic and video traffic.
To address the demand for data communication services, the use of optical networks, such as a synchronous optical network (SONET), is becoming more prevalent. A SONET network is an example of a time division multiplexed (TDM) network. TDM networks generally allocate single lines to be used amongst multiple users, or customers of data communication services. The single lines may each be divided into slots of time during which each user has access to the single lines.
A network such as a TDM network is generally designed to ensure that information may be transferred between nodes within the network. Often, within a network, information is transferred between two specified nodes, i.e., a source node which sends information and a destination node which receives information. When information is to be sent between a source node and a destination node, a circuit path between the two nodes must be computed so that leased line services may be provided.
In general, a network may include at least one bi-directional line switched ring (BLSR). A BLSR generally allows data traffic to be sent in opposite directions. That is, for a bi-directional ring, traffic is typically routed such that both directions of a two-way connection travel along the ring using the same ring nodes, but in opposite directions. A BLSR may typically include either two fibers or four fibers. A two fiber BLSR is a ring in which traffic is normally routed in both directions, i.e., in a clockwise direction and a counter-clockwise direction.
FIG. 1a is a diagrammatic representation of a BLSR which may be part of a network. A BLSR 104 includes network elements such as nodes 108 and fibers 112. Nodes 108 are communicably connected to other nodes 108 using fibers 112. BLSR 104, as shown, is a two-fiber BLSR as any link between two nodes 108 uses two fibers 112. Within BLSR 104, when data traffic is to travel between node A 108a and node B 108b, the point or node 108b at which the data traffic enters determines the direction in which the data traffic is routed.
When data traffic enters at node A 108a and is to exit at node B 108b, then the data traffic travels in a substantially clockwise direction 116 along fiber 112a. Alternatively, when data traffic enters at node B 108b and is to exit at node A 108a, then the data traffic travels in a substantially counter-clockwise direction 120 along fiber 112b. 
When a fiber, e.g., fiber 112a, fails, that fiber may no longer be used to route data traffic. That is, when fiber 112a fails, fiber 112a may not be used to transfer data between node A 108a and node B 108b in a clockwise direction. As fiber 112b is used to transfer data between node B 108b and node A 108a in a counter-clockwise direction, data typically may not be routed from node A 108a to node B 108b using fiber 112b. Hence, when fiber 112a fails, an attempt generally must be made to identify an alternate route between node A 108a and node B 108b. 
With reference to FIG. 1b, the identification of an alternate path between nodes, i.e., node A 108a and node B 108b, will be described. Within BLSR 104, when fiber 112a fails, an alternate path which routes data traffic in a clockwise direction from node A 108a to node B 108b is identified to allow data traffic to be routed to node B 108b from node A 108a. As shown, an alternate counter-clockwise or anti-clockwise path 124 from node A 108a to node B 108b uses fiber 112g, fiber 112e, and fiber 112c. That is, alternate path 124 passes from node A 108a to node C 108c using fiber 112g, passes from node C 108c to node D 108d using fiber 112e, and passes from node D 108d to node B 108b through fiber 112c. 
Typically, within a BLSR, there are protected time slots or channels. Specifically, each fiber within a BLSR may be divided into channels. By way of example, if a fiber is a link which meets OC-48 requirements associated with SONET standards, i.e., if a fiber is an OC-48 link, then the fiber has twenty four working channels or time slots and twenty four protected channels or time slots. The twenty four working channels may be the first twenty-four channels on a OC-48 link, while the twenty four protected channels may be the last twenty-four channels on the OC-48 link.
Working channels of a fiber or a link are allocated for use to transfer data between nodes which are communicably connected by the fiber or the link. The number of available channels on a link at any given time effectively defines the bandwidth on the link. FIG. 2a is a diagrammatic representation of two fibers between nodes that a part of a BLSR. A node A 204 and a node B 208 are in communication through fibers 212, 216. Fiber 212 may be arranged to transfer data from node A 204 to node B 208, whereas fiber 216 may be used to transfer data from node B 208 to node A 204. That is, fiber 212 may be used to transfer data in a clockwise direction from node A 204 to node B 208, while fiber 216 may be used to transfer data in a counter-clockwise direction from node B 208 to node A 204.
Fiber 212 includes channels 220, or time slots, and fiber 216 includes channels 224. Channels 220, 224 include both working channels, i.e., channels through which data is routed under most conditions, and protected channels, i.e., channels through which circuit paths are routed when a selected working channel fails. As will be appreciated by those skilled in the art, a working channel generally has an associated protected channel. By way of example, if fibers 212, 216 are OC-48 links, then a working channel in a fifth time slot associated with fiber 212 is associated with a protected channel in a twenty-ninth time slot associated with a different fiber. In the event that the fifth time slot goes down, the data that was intended to be transferred through the fifth time slot is transferred through the twenty-ninth time slot instead.
Typically, within a BLSR, time slots used to transfer data must be consistent, i.e., the same. In other words, if data is to be transferred from node A 204 to node B 208, then from node B 208 to another node, the channel 220 used in fiber 212 must be the same as the channel used in a link between node B 208 and the other node. As shown in FIG. 2b, if data is transferred across a channel ‘5’ 220a from node A 204 to node B 208, then that same data is transferred across a channel ‘5’ 256a on a link 252 between node B 208 and a node C 248.
The use of consistent time slots throughout a circuit path segment in a BLSR substantially ensures that the failure of a link between a source node and a destination node does not prevent data from being successfully transmitted between the source node and the destination node. For instance, referring back to FIG. 1b, 1f a transmission is intended to be sent from node A 108a to node B 108b on channel “5” across link 112a, and link 112a fails, then the transmission is sent from node A 108a to node B 108 on channel “29” on link 112g, link 112e, and link 112c. As discussed above, working channel “5” is associated with protected channel “29.” If inconsistent channels are used in a circuit path segment, e.g., if channel “5” 220a and channel “7” 256b as shown in FIG. 2c are used, to transmit data between two nodes then if one of the channels fails and node B 108b fails, the destination node is not aware of whether it should expect a transmission over a protected channel “29” or a protected channel “31,” as specified by BLSR protocols. Hence, the transmission of the signal may be unacceptably delayed while it is determined which channel the destination node should expect a transmission from. It should be appreciated that if node B 108b is “alive,” node B 108b may convert channel “29” to channel “5.”
Circuit paths are often protected such that a failure of a node associated with a path does not prevent data which would have been routed through the path from being successfully transmitted. In general, substantially all network links of a BLSR much use the same channels or time slots such that a path which uses the network links is protected even when a node fails. For example, if an intermediate node between a source node and a destination node fails, then the use of consistent channels allows the destination node to be substantially instantly aware of which protected channel of an alternate route to expect a transmission to be received over.
Identifying time slots which are available throughout a BLSR is generally a task that is performed by a network administrator. Typically, each node of a BLSR is aware of which channels or time slots are available on physical links which are associated with the BLSR. Hence, the network administrator may access substantially any node in the BLSR to determine which channels are available for routing a circuit path segment through the BLSR. FIG. 2c is a diagrammatic representation of nodes A 204, node B 208, and node C 248 of FIG. 2b. For ease of illustration, only channels of fibers 212, 252 are shown. When a path through a BLSR ring is to be created beginning at node A 204, e.g., a source node, and ending at node C 248, e.g., an end node, to ensure that a protected path is possible even in the event of a nodal failure, it is determined which working channels are available between node A 204 and node B 208, as well as between node B 208 and node C 248.
As will be appreciated by those skilled in the art, node A 204 is aware of which channels 220 are available between node A 204 and node B 208, as well as all other channels within a BLSR. If channel ‘5’ 220a is available between node A 204 and node B 208, but substantially only channel ‘7’ 256b is available between node B 208 and node C 248, then if protection in the event of a nodal failure is desired, it must be determined if channel ‘7’ between node A 204 and node B 208 is available for use.
When a circuit path that uses a BLSR to be routed, a network administrator conventionally studies the available channels between nodes of the BLSR through which a circuit path is to be created. Then, the network administrator manually selects the channel which is to be used between all nodes of the BLSR, and creates the circuit path through the selected channel, e.g., when a path protection is desired. Manually routing a path between a source node and a destination node in a BLSR such that each link uses the same time slot is time consuming and, hence, inefficient, particularly in large networks. For instance, BLSRs may include up to sixteen nodes. Further, when a path is manually routed, the likelihood that the path is routed incorrectly increases. Such an error may cause an overall network to operate inefficiently.
Therefore, what is needed is an efficient method and apparatus for causing network links in a BLSR to use the same time slot. That is, what is desired is an efficient system which enables links of a circuit path within a BLSR which use the same time slots to be created substantially automatically.